/*
 * @lc app=leetcode.cn id=5 lang=swift
 *
 * [5] 最长回文子串
 */

// @lc code=start

class Solution {
    var palindromeText: String!
    func longestPalindrome(_ s: String) -> String {
        let characters = Array(s)
        var dp = [[Bool]](repeating: [Bool](repeating: false, count: characters.count), count: characters.count)
        for i in 0 ..< characters.count {
            dp[i][i] = true
        }
        
        var maxLength = 1
        var begin = 0
        for j in 1 ..< characters.count {
            for i in 0 ..< j {
                if characters[i] != characters[j] {
                    dp[i][j] = false
                }else if j - i < 3 {
                    dp[i][j] = true
                }else{
                    dp[i][j] = dp[i+1][j-1]
                }
                
                if dp[i][j] {
                    let palindromeLength = j - i + 1
                    if palindromeLength > maxLength {
                        maxLength = palindromeLength
                        begin = i
                    }
                }
            }
        }
        
        return String(characters[begin ..< begin + maxLength])
    }
    
}

// @lc code=end

